package com.gitee.feizns.explore.data_structure.stack.min_stack;

import java.util.function.Consumer;

/**
 * @author feizns
 * @since 2019/10/11
 */
public class MinStack {

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.getMin());
        System.out.println("============");
        stack.forEach(System.out::println);
        stack.pop();
        System.out.println(stack.getMin());
        System.out.println("============");
        stack.forEach(System.out::println);
    }

    private Stack data = new Stack();

    private Stack min = new Stack();

    public void push(int x) {
        data.push(x);
        if ( min.isEmpty() || x <= min.peek() )
            min.push(x);
    }

    public void pop() {
        int val = data.pop();
        if ( val == min.peek() )
            min.pop();
    }

    public int top() {
        return data.peek();
    }

    public int getMin() {
        return min.peek();
    }

    public void forEach(Consumer<Integer> consumer) {
        data.forEach(consumer);
    }

}

class Node {

    int val;

    Node next;

    public Node(int val) {
        this.val = val;
    }
}

class Stack {

    private Node head = new Node(-1);

    public void push(int v) {
        Node next = head.next;
        head.next = new Node(v);
        head.next.next = next;
    }

    public int pop() {
        if ( isEmpty() )
            throw new RuntimeException("Stack is empty!");
        int ret = head.next.val;
        head.next = head.next.next;
        return ret;
    }

    public int peek() {
        if ( isEmpty() )
            throw new RuntimeException("Stack is empty!");
        return head.next.val;
    }

    public boolean isEmpty() {
        return head.next == null;
    }

    public void forEach(Consumer<Integer> consumer) {
        for (Node curt = head.next; curt != null; curt = curt.next) {
            consumer.accept(curt.val);
        }
    }

}
